# 递归不需要同学们掌握,需要的是有所了解
# 递归是一种算法
# 算法: 将数学知识转换为编程代码的一种思想

# 需求: 计算1-100的累加和   f(x) 这个函数代表 1-x的累加和
'''
总结规律
f(1) = 1
f(2) = 1 + 2 = f(1) + 2
f(3) = 1 + 2 + 3 = f(2) + 3
f(4) = 1 + 2 + 3 + 4 = f(3) + 4
....
f(n) = 1 + 2 + 3.... + n = f(n-1) + n

最终规律: f(n) = f(n-1) + n
'''


# 递归就是在函数体内调用函数本身的计算方法.
def sum1(n):
    return sum1(n - 1) + n


# RecursionError: maximum recursion depth exceeded
# 超出函数的最大调用深度(python中默认最大调用深度为1000) , 由于此处没有明确的递归出口,所以函数将无限递归下去
# print(sum1(5))

# 解决问题: 当n = 1 时, 我们发现不需要继续调用函数,可以直接返回1, 此时我们就具备了递归出口

def sum2(n):
    if n == 1:
        return 1
    return sum2(n - 1) + n


print(sum2(5))
print(sum2(100)) # 5050


# 有效递归的注意事项:
# 1.函数定义的内部必须调用函数本身
# 2.要有明确的函数跳出条件
# 3.不超出最大调用深度, Python默认是1000层
# RecursionError: maximum recursion depth exceeded in comparison
# 系统默认函数嵌套超过1000层就会报错,所以我们要保证我们的递归在循环调用函数时不超过1000层,否则就会报错
print(sum2(997))


# 注意: 开发中尽量不要使用
# 1.递归效率极低
# 2.递归的业务应用场景不多见,一般出现在算法中
# 3.极易出错


# 举例: 斐波那契数列(第三个数是前两个数之和)
# 1 1 2 3 5 8 13 21 ......

def Fibonacci(n):
    # 递归出口,当n = 1 或者 n = 2 时 值为 1
    if n in (1, 2):
        return 1
    return Fibonacci(n - 2) + Fibonacci(n - 1)

# 使用上述函数计算,如果计算数值较大,则无法快速算出数据,计算性能较差,效率较低
print(Fibonacci(40))
